package zuochengyun.chapter5;

//最小包含子串的长度

//字符串A包含字符串B的所有字符的最小长度
public class MinContainSubSequence {

	public static void main(String[] args) {
		String str1 = "adabbc";
		String str2 = "abc";
		MinContainSubSequence object = new MinContainSubSequence();
		System.out.println(object.minLength(str1, str2));
	}
	
	//返回最小的长度
	public int minLength(String str1, String str2){
		if(str1 == null || str2 == null || str1.length() < str2.length() ){
			return 0;
		}
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		//map表示对于chars1而言，还欠chars2字符的个数
		//比如ababncdbbc   abc， map初始就是a -- 1; b -- 1; c -- 1.
		int[] map = new int[256];
		for (int i = 0; i < chars2.length; i++) {
			map[chars2[i]]++;
		}
		
		//表示str1的左右边界
		int left = 0;
		int right = 0;
		
		int match = chars2.length;  //用于表示还未匹配的个数，为0表示全部匹配
		int length = Integer.MAX_VALUE;
		while(right != chars1.length){
			map[chars1[right]]--;    //详见P292，如果map[chars1[right]]为0就会减成负的
			//如果减了之后大于等于0，那么就说明chars2中有这个字符，将match减1
			if(map[chars1[right]] >= 0){
				match--;
			}
			if(match == 0){
				//如果match为0，就是说明已经包含了全部，但是不一定是最小的
				//此时可以移动left,将map中为负的(表示chars2中不含有的)移除
				while(map[chars1[left]] < 0){
					map[chars1[left++]]++;
				}
				//将所有的能够清楚的之后 ，就更新length的值
				length = Math.min(length, right - left + 1);
				//因为以left开始的最短子串已经记录了，所以要将left移动一位，并将，match++
				map[chars1[left++]]++;
				match++;
			}
			right++;
		}
		return length == Integer.MAX_VALUE ? 0 : length;
	}
	
	//最小的包含所有字符的子串
	public String minWindow(String str1, String str2){
		if(str1 == null || str2 == null || str1.length() < str2.length() ){
			return "";
		}
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		//map表示对于chars1而言，还欠chars2字符的个数
		//比如ababncdbbc   abc， map初始就是a -- 1; b -- 1; c -- 1.
		int[] map = new int[256];
		for (int i = 0; i < chars2.length; i++) {
			map[chars2[i]]++;
		}
		
		//表示str1的左右边界
		int left = 0;
		int right = 0;
		int start = 0;
		int match = chars2.length;  //用于表示还未匹配的个数，为0表示全部匹配
		int length = Integer.MAX_VALUE;
		while(right != chars1.length){
			map[chars1[right]]--;    //详见P292，如果map[chars1[right]]为0就会减成负的
			//如果减了之后大于等于0，那么就说明chars2中有这个字符，将match减1
			if(map[chars1[right]] >= 0){
				match--;
			}
			if(match == 0){
				//如果match为0，就是说明已经包含了全部，但是不一定是最小的
				//此时可以移动left,将map中为负的(表示chars2中不含有的)移除
				while(map[chars1[left]] < 0){
					map[chars1[left++]]++;
				}
				//将所有的能够清除的清除之后 ，就更新length的值
				if(right - left + 1 < length){
					length = right - left + 1;
					start = left;
				}
				//因为以left开始的最短子串已经记录了，所以要将left移动一位，并将，match++
				map[chars1[left++]]++;
				match++;
			}
			right++;
		}
		if(length == Integer.MAX_VALUE) return "";
		return str1.substring(start, start + length);
	}
}
